package _每日一题._2020年._20年7月;

/**
 * @author lerry-lee
 * @version 1.0
 * @create 2020/07/12 11:47
 * @description 硬币
 * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 * <p>
 * 示例1:
 * <p>
 * 输入: n = 5
 * 输出：2
 * 解释: 有两种方式可以凑成总金额:
 * 5=5
 * 5=1+1+1+1+1
 * 示例2:
 * <p>
 * 输入: n = 10
 * 输出：4
 * 解释: 有四种方式可以凑成总金额:
 * 10=10
 * 10=5+5
 * 10=5+1+1+1+1+1
 * 10=1+1+1+1+1+1+1+1+1+1
 */
public class _08dot11硬币 {
    /**
     * 思路1：动态规划
     * 1.状态定义：
     * （1）coins={1,5,10,25}表示硬币币值数组
     * （2）dp[i]表示面额为i时的不同的硬币币值表示个数
     * ①那么dp[i]+=dp[i-coin]，表示面额为i的表示个数加等于面额为i-coin的表示个数
     * ②例如：dp[10]表示面额为10时的表示个数，结果为dp[10]+dp[10-10]+dp[10-5]+dp[10-1]，其中dp[10]为0，dp[0]为1表示用一张币值和面额相同的可以表示；dp[5]和dp[9]由之前的值得到
     * 2.状态转移：
     * dp[i]+=dp[i-coin],coin∈coins
     * 3.初始化：
     * dp[0]=1表示面额和币值相同时可以用一枚币值等于面额的硬币表示，此时表示个数为1
     * <p>
     * Tips：先升序遍历币值可解决重复算数问题
     */
    public int waysToChange(int n) {
        int[] coins = {1, 5, 10, 25};
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}
